package leetcode.hot100;

public class Solution287 {

    public static void main(String[] args) {

        int[] nums = {1,3,4,2,2};
        System.out.println(new Solution287().findDuplicate(nums));

    }

    public int findDuplicate1(int[] nums) {
        int n = nums.length, min = 1, max = n, mid;
        //在min和max之间进行查找，找到第一个cnti>i的数字，其中cnt是nums中小于等于i的数字个数
        while (min<=max){
            mid = (min+max)>>1;
            //统计cnt
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if(nums[i]<=mid) cnt++;
            }
            //二分
            if(cnt>mid) max = mid-1;
            else min = mid+1;
        }
        return max+1;
    }

    /**
     * 作为环的快慢指针
     * @param nums
     * @return
     */
    public int findDuplicate(int[] nums) {
        //快慢指针
        int slow = 0, fast = slow;
        do{
            slow = nums[slow];
            fast = nums[fast];
            fast = nums[fast];
        }while(slow!=fast);

        //相等了，快指针回到头
        fast = 0;
        while(slow!=fast){
            slow = nums[slow];
            fast = nums[fast];
        }
        //第二次相遇处即为环入口
        return slow;
    }

}
